package codingforgreat.lchot150;

import java.util.*;

public class Lc218 {
    public class Node{
        int x;
        boolean isAdd;
        int h;
        public Node(int x, boolean isAdd, int h) {
            this.x = x;
            this.isAdd = isAdd;
            this.h = h;
        }
    }
    public List<List<Integer>> getSkyline(int[][] buildings) {
        String s = " abv ";
       char[] str = s.replace(" ","").toCharArray();
        Node[] nodes = new Node[buildings.length * 2];
        int index = 0;
        for(int[] building : buildings){
            nodes[index++] = new Node(building[0], true, building[2]);
            nodes[index++] = new Node(building[1], false, building[2]);
        }
        Arrays.sort(nodes,(o1,o2) ->{return o1.x == o2.x ? o1.isAdd ? -1 : 1 : o1.x - o2.x;});
        List<List<Integer>> res = new ArrayList<>();
        TreeMap<Integer,Integer> heightTimes = new TreeMap<>();
        LinkedHashMap<Integer, Integer> mapXHeight = new LinkedHashMap<>();
        for(int i = 0; i < nodes.length;i++){
            if(nodes[i].isAdd){
                if(!heightTimes.containsKey(nodes[i].h)){
                    heightTimes.put(nodes[i].h,1);
                }else{
                    heightTimes.put(nodes[i].h,heightTimes.get(nodes[i].h) + 1);
                }
            }else{
                heightTimes.put(nodes[i].h, heightTimes.get(nodes[i].h) - 1);
                if (heightTimes.get(nodes[i].h) == 0) {
                    heightTimes.remove(nodes[i].h);
                }
            }
            if (heightTimes.isEmpty()) {
                mapXHeight.put(nodes[i].x, 0);
            } else {
                mapXHeight.put(nodes[i].x, heightTimes.lastKey());
            }
        }
        mapXHeight.forEach((x, h) -> {
            if (res.isEmpty() || res.get(res.size() - 1).get(1) != h) {
                res.add(new ArrayList<>(Arrays.asList(x, h)));
            }
        });
        return res;

    }
}
